package com.linyaonan.leetcode.easy._784;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。
 * <p>
 * 示例:
 * 输入: S = "a1b2"
 * 输出: ["a1b2", "a1B2", "A1b2", "A1B2"]
 * <p>
 * 输入: S = "3z4"
 * 输出: ["3z4", "3Z4"]
 * <p>
 * 输入: S = "12345"
 * 输出: ["12345"]
 * 注意：
 * <p>
 * S 的长度不超过12。
 * S 仅由数字和字母组成。
 *
 * @author: Lin
 * @date: 2020/1/5
 */
public class LetterCasePermutation {

    public List<String> letterCasePermutation(String S) {
        List<String> ans = new ArrayList<>();
        dg(S.toCharArray(), 0, ans);
        return ans;
    }

    private void dg(char[] s, int i, List<String> ans) {
        if (i == s.length) {
            ans.add(String.valueOf(s));
            return;
        }
        dg(s, i + 1, ans);
        if (s[i] < '0' || s[i] > '9') {
            s[i] ^= (1 << 5);
            dg(s, i + 1, ans);
        }

    }
}
